
class Compare:

    def __init__(self, tree1, tree2):
        self.tree1 = tree1
        self.tree2 = tree2
        print tree1
        print tree2

    def compareBinary(self):
        tree1 = self.tree1.getRoot().getChild1()
        tree2 = self.tree2.getRoot().getChild1()
        return self.iterateBinary(tree1, tree2)

    def iterateBinary(self, tree1, tree2):
        comparison = False
        if tree1 is None and tree2 is None:
            comparison = True
        elif tree1 is None and tree2 is not None:
            comparison = False
        elif tree1 is not None and tree2 is None:
            comparison = False
        elif tree1.getLabel() == tree2.getLabel():
            print "Tree 1: %s, Tree 2: %s" % (tree1.getLabel(), tree2.getLabel())
            comparison = True
            comparison = comparison and self.iterateBinary(tree1.getChild1(), tree2.getChild1())
            comparison = comparison and self.iterateBinary(tree1.getChild2(), tree2.getChild2())
        else:
            comparison = False
        return comparison

    def rotation_distance(self):
        tree1Nodes = []
        tree2Nodes = []
        for node in self.tree1.iterator(self.tree1.getRoot()):
            tree1Nodes.append(node)
        for node in self.tree2.iterator(self.tree2.getRoot()):
            tree2Nodes.append(node)
        if len(tree1Nodes) >= len(tree2Nodes):
            distance = self.move_root(self.tree1.getRoot().getChild1(), self.tree2, self.tree2.getRoot().getChild1())
            print "Distance: %d" % (distance)
            return distance
        else:
            distance = self.move_root(self.tree2.getRoot().getChild1(), self.tree1, self.tree1.getRoot().getChild1())
            print "Distance: %d" % (distance)
            return distance

    def move_root(self, root, sub, rootSub):
        distance = 0
        #print "rootSub " + rootSub.getLabel()
        label = root.getLabel()
        if label == rootSub.getLabel():
            return 0
        for node in sub.iterator(rootSub):
            if node.getLabel() == label:
                #print sub.toString()
                check = True
                while  check:
                    print "Change " + node.getLabel()
                    print "Parent: " + node.getParent().getLabel()
                    node.rotation()
                    #print sub.toString()
                    distance = distance + 1
                    if node.getChild1() is not None:
                        if node.getChild1().getLabel() is rootSub.getLabel():
                            check = False
                    if node.getChild2() is not None:
                        if node.getChild2().getLabel() is rootSub.getLabel():
                            check = False
                rootSub = node
                break
        if rootSub.getChild1() is not None and root.getChild1() is not None:
            if rootSub.getChild1().getChild1() is not None or rootSub.getChild1().getChild2() is not None:
                distance = distance + self.move_root(root.getChild1(), sub, rootSub.getChild1())
                print distance
        if rootSub.getChild2() is not None and root.getChild2() is not None:
            if rootSub.getChild2().getChild1() is not None or rootSub.getChild2().getChild2() is not None:
                distance = distance + self.move_root(root.getChild2(), sub, rootSub.getChild2())
                print distance
        return distance

    def determine_switch(self, main, sub, mainRoot, root):
        mainChild1 = {}
        mainChild2 = {}
        subChild1 = []
        subChild2 = []
        for node in main.iterator(mainRoot.getChild1()):
            mainChild1[node.getLabel()] = node
        for node in main.iterator(mainRoot.getChild2()):
            mainChild2[node.getLabel()] = node
        for node in sub.iterator(root.getChild1()):
            subChild1.append(node)
            if node.getLabel() in mainChild2.keys():
                parent = mainChild2[node.getLabel()].getParent()
                if parent.getChild1() == mainChild2[node.getLabel()]:
                    self.switch()
                else:
                    self.switch()
        for node in sub.iterator(root.getChild2()):
            subChild2.append(node)
            if node.getLabel() in mainChild1.keys():
                self.switch()

    def switch(self, parent1, child1, parent2, child2):
        if child1 == 1:
            parent1Child = parent1.getChild1()
            if child2 == 1:
                parent2Child = parent.getChild1()
                parent1.setChild1(parent2Child)
                parent2.setChild1(paren1Child)
            elif child2 == 2:
                parent2Child = parent.getChild2()
                parent1.setChild1(parent2Child)
                parent2.setChild2(paren1Child)
        elif child2 == 2:
            parent1Child = parent1.getChild2()
            if child2 == 1:
                parent2Child = parent.getChild1()
                parent1.setChild2(parent2Child)
                parent2.setChild1(paren1Child)
            elif child2 == 2:
                parent2Child = parent.getChild2()
                parent1.setChild2(parent2Child)
                parent2.setChild2(paren1Child)

    def determine_relabel(self):
        return

    def relabel(self, node, label):
        node.setLabel(label)

    

    
            
